-- 2022-8-17

--[[ 18.3 无状态迭代器

    顾名思义 无状态迭代器(stateless iterator)就是一种自身不保存任何状态的迭代器
    因此 可以在多个循环中使用同一个无状态迭代器 从而避免创建新闭包的开销

    正如刚刚所看到的 for循环会以不可变状态和控制变量为参数调用迭代函数 一个无状态迭代器只根据这两个值来为迭代生成下一个元素
    这类迭代器的一个典型例子就是ipairs 它可以迭代一个序列中的所有元素
    a = {"one","two","three"}
    for i,v in ipairs(a) do
        print(i,v)
    end
    迭代的状态由正在被遍历的表(一个不可变状态 它不会在循环中改变)及当前的索引值(控制变量)组成
    ipair(工厂)和迭代器都非常简单 我们可以在Lua语言中将其编写出来:
    local function iter (t,i)
        i = i + 1
        local v = t[i]
        if v then
            return i,v
        end
    end

    function ipairs(t)
        return iter,t,0
    end

    当调用for循环中的ipairs(t)时 ipairs(t)会返回三个值 即迭代函数iter 不可变状态表t和控制变量的初始值0
    然后 Lua语言调用iter(t,0) 得到1,t[1](除非t[1]已经变成了nil)
    在第二次迭代中 Lua语言调用iter(t,1) 得到2,t[2],依次类推 直至得到第一个为nil的元素

    函数pairs与函数ipairs类似 也用于遍历一个表中的所有元素 不同的是 函数pairs的迭代函数是Lua语言中的一个基本函数next:
    function pairs (t)
        return next,t,nil
    end
    
    在调用next(t,k)时 k是表t的一个键 该函数会以随机次序返回表中的下一个键及k对应的值(作为第二个返回值)
    调用next(t,nil)时 返回表中的第一个键值对 当所有元素被遍历完时 函数next返回nil
    我们可以不调用pairs而直接使用next:
    for k,v in next,t do
        loop body
    end
    请注意 for循环会把表达式列表的结果调整为三个值 因此上例中得到的是next t和nil 这也正与pairs(t)的返回值完全一致

    关于无状态迭代器的另一个有趣的示例是遍历链表的迭代器(链表在Lua语言中并不常见 但有时也需要用到)
    我们的第一反应可能是只把当前节点当作控制变量 以便于迭代函数能够返回下一个节点
    local function getnext (node)
        return node.next
    end
    function traverse (list)
        return getnext,nil,list
    end
    但是 这种实现会跳过第一个节点 所以 我们需要使用如下的代码:
    local function getnext(list,node)
        if not node then
            return list
        else
            return node.next
        end
    end
    function traverse (list)
        return getnext,list,nil
    end
    这里的技巧是 除了将当前节点作为控制变量 还要将头节点作为不可变状态(traverse返回的第二个值)
    第一个调用迭代函数getnext时 node为nil 因此函数返回list作为第一个节点
    在后续的调用中 node不再是nil 所以迭代函数会像我们所期望的那样返回node.next
]]